package leetcode.每日一题;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ：zsy
 * @date ：Created 2022/10/17 9:50 AM
 * @description：https://leetcode.cn/problems/fruit-into-baskets/
 */
public class 水果成篮 {
    @Test
    public void test() {
        System.out.println(new Solution().totalFruit(new int[]{3,3,3,1,2,1,1,2,3,3,4}));
    }

    /*class Solution {
        public int totalFruit(int[] fruits) {
            if (fruits.length == 0) return 0;
            int max = 0;
            int startIdx = 0;
            Map<Integer, Integer> map = new HashMap<>();
            int A = fruits[0], B = -1;
            map.put(A, 0);
            int i;
            for (i = 0; i < fruits.length; i++) {
                if (fruits[i] != A) {
                    map.put(A, i - 1);
                    B = fruits[i];
                    break;
                }
            }
            for (; i < fruits.length; i++) {
                if (fruits[i] != B) {
                    map.put(B, i - 1);
                    break;
                }
            }
            for (; i < fruits.length; i++) {
                if (map.containsKey(fruits[i])) {
                    map.put(fruits[i], i);
                    continue;
                }
                if (map.size() >= 2) {
                    max = Math.max(max, i - startIdx);
                    map.put(fruits[i], i);
                    int preNum;
                    if (map.get(A) < map.get(B)) {
                        preNum = A;
                        A = fruits[i];
                    } else {
                        preNum = B;
                        B = fruits[i];
                    }
                    startIdx = map.remove(preNum) + 1;
                }
            }
            return Math.max(max, fruits.length - startIdx);
        }
    }*/

    /*class Solution {
        public int totalFruit(int[] fruits) {
            Map<Integer, Integer> map = new HashMap<>();
            int left = 0;
            int ans = 0;
            for (int right = 0; right < fruits.length; right++) {
                map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
                while (map.size() > 2) {
                    map.put(fruits[left], map.get(fruits[left]) - 1);
                    if (map.get(fruits[left]) == 0) {
                        map.remove(fruits[left]);
                    }
                    left++;
                }
                ans = Math.max(ans, right - left + 1);
            }
            return ans;
        }
    }*/

    class Solution {
        public int totalFruit(int[] fruits) {
            int n = fruits.length;
            int ans = 0;
            int[] cnts = new int[n + 10];
            for (int i = 0, j = 0, tot = 0; i < n; i++) {
                if (++cnts[fruits[i]] == 1) tot++;
                while (tot > 2) {
                    if (--cnts[fruits[j++]] == 0) tot--;
                }
                ans = Math.max(ans, i - j + 1);
            }
            return ans;
        }
    }

}
